{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Subarray Sum After One Operation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSumAfterOperation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #经过一次操作后的最大子数组和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有一个整数数组 <code>nums</code>。你只能将一个元素 <code>nums[i]</code> 替换为 <code>nums[i] * nums[i]</code>。</p>\n",
    "\n",
    "<p>返回替换后的最大子数组和。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,-1,-4,-3]\n",
    "<strong>输出：</strong>17\n",
    "<strong>解释：</strong>你可以把-4替换为16(-4*(-4))，使nums = [2,-1,<strong>16</strong>,-3]. 现在，最大子数组和为 2 + -1 + 16 = 17.</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,-1,1,1,-1,-1,1]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>你可以把第一个-1替换为1，使 nums = [1,<strong>1</strong>,1,1,-1,-1,1]. 现在，最大子数组和为 1 + 1 + 1 + 1 = 4.</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-subarray-sum-after-one-operation](https://leetcode.cn/problems/maximum-subarray-sum-after-one-operation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-subarray-sum-after-one-operation](https://leetcode.cn/problems/maximum-subarray-sum-after-one-operation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,-1,-4,-3]', '[1,-1,1,1,-1,-1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        res=dp0=dp1=-float('inf')\n",
    "        for i in range(len(nums)):\n",
    "            dp1 = max(dp0+nums[i]*nums[i],nums[i]*nums[i],dp1+nums[i])\n",
    "            dp0 = max(dp0+nums[i],nums[i])\n",
    "            res = max(res,dp1,dp0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        sq = nums[0]*nums[0]\n",
    "        nosq = nums[0]\n",
    "\n",
    "        res = sq\n",
    "\n",
    "        for i in range(1,len(nums)):\n",
    "            sq = max(sq+nums[i],nosq+nums[i]*nums[i])\n",
    "            nosq = max(0,nosq + nums[i])\n",
    "            res = max(res,sq)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # sq,nosq=nums[0]*nums[0],nums[0]\n",
    "        # res=sq\n",
    "        # for i in range(1,len(nums)):\n",
    "        #     sq=max(sq+nums[i],nosq+nums[i]*nums[i])\n",
    "        #     nosq=max(0,nosq+nums[i])\n",
    "        #     res=max(res,sq)\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        # n = len(nums)\n",
    "        # left, right = 0, n - 1\n",
    "        # max_sum = float('-inf')\n",
    "    \n",
    "        # while left <= right:\n",
    "        #     left_square = nums[left] * nums[left]\n",
    "        #     right_square = nums[right] * nums[right]\n",
    "        \n",
    "        #     if left_square >= right_square:\n",
    "        #         max_sum = max(max_sum + nums[left], max_sum)\n",
    "        #         left += 1\n",
    "        #     else:\n",
    "        #         max_sum = max(max_sum + nums[right], max_sum)\n",
    "        #         right -= 1\n",
    "            \n",
    "        # return max_sum\n",
    "        # 整数的平方都不小于这个整数，包括0\n",
    "        # 因此dp1不再需要额外的更新，只需要更新dp2即可\n",
    "        # dp2+nums[i]*nums[i]即使在更新dp1的时候被采用也不要紧,因为dp2会以dp2+nums[i]的方式更新，而不是按照dp2+nums[i]*nums[i]的方式更新\n",
    "        dp1 = dp2 =0\n",
    "        max_num = 0\n",
    "        for i in range(len(nums)):\n",
    "            dp1 = max(dp1+nums[i], dp2+nums[i]*nums[i])\n",
    "            dp2 =max(dp2+nums[i],0)\n",
    "            max_num = max(dp1, max_num)\n",
    "        return max_num\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "\n",
    "        res, dp0, dp1 = -float('inf'), -float('inf'), -float('inf')\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            \n",
    "            dp1 = max(dp0 + nums[i]**2, dp1 + nums[i], nums[i]**2)\n",
    "            dp0 = max(dp0 + nums[i], nums[i])\n",
    "            res = max(res, dp0, dp1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        dp1, dp2, ans = 0, 0, 0\n",
    "        for num in nums:\n",
    "            dp1, dp2 = max(dp1 + num, dp2 + num ** 2), max(0, dp2 + num)\n",
    "            ans = max(dp1, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        if not nums:\n",
    "            return res\n",
    "        len_n = len(nums)\n",
    "        replace = 0\n",
    "        noreplace = 0\n",
    "        res = nums[0]\n",
    "        for i in range(len_n):\n",
    "            replace = max(nums[i]*nums[i],nums[i]+replace,nums[i]*nums[i]+noreplace)\n",
    "            noreplace = max(nums[i],nums[i]+noreplace)\n",
    "            res = max(res,replace)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        sq, nosq = nums[0] * nums[0], nums[0]\n",
    "        res = sq\n",
    "        for i in range(1, len(nums)):\n",
    "            sq = max(sq + nums[i], nosq + nums[i] * nums[i])\n",
    "            nosq = max(0, nosq + nums[i])\n",
    "            res = max(res, sq)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        res = dp0 = dp1 = float('-inf')\n",
    "        for i in range(len(nums)):\n",
    "            dp1 = max(dp0 + nums[i]*nums[i], dp1+nums[i], nums[i]* nums[i])\n",
    "            dp0 = max(dp0+nums[i], nums[i])\n",
    "            res = max(res, dp0, dp1)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        res = dp0=dp1=-float('inf')\n",
    "        for i in range(len(nums)):\n",
    "            dp1 = max(dp0+nums[i]*nums[i],nums[i]*nums[i],dp1+nums[i])\n",
    "            dp0= max(dp0+nums[i],nums[i])\n",
    "            res =max(res,dp1,dp0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        res = dp0 = dp1 = float('-inf')\n",
    "        for i in range(len(nums)):\n",
    "            dp1 = max(dp0+nums[i]**2, nums[i]**2, dp1+nums[i])\n",
    "            dp0 = max(dp0 + nums[i], nums[i])\n",
    "            res = max(dp0, dp1, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        res = dp0 = dp1 = float('-inf')\n",
    "        for i in range(len(nums)):\n",
    "            dp1 = max(dp0 + nums[i]**2, nums[i]**2, dp1 + nums[i])\n",
    "            dp0 = max(dp0 + nums[i], nums[i])\n",
    "            res = max(dp0, dp1, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        dp_no_modify = nums[0]\n",
    "        dp_modified = nums[0] * nums[0]\n",
    "        rst = dp_modified\n",
    "\n",
    "        for num in nums[1:]:\n",
    "            dp_no_modify = max(0, dp_no_modify)\n",
    "            dp_modified = max(dp_no_modify + num * num, dp_modified + num)\n",
    "            dp_no_modify += num\n",
    "\n",
    "            rst = max(rst, dp_modified)\n",
    "\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        dp = [0] * 2\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = nums[0] ** 2\n",
    "        res = dp[1]\n",
    "        for i in range(1, len(nums)):\n",
    "            dp[0] = max(dp[0], 0)\n",
    "            dp[1] = max(dp[0] + nums[i]**2, dp[1] + nums[i])\n",
    "            dp[0] += nums[i]\n",
    "            res = max(res, dp[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        res = dp0 = dp1 = float('-inf')\n",
    "        for i in range(len(nums)):\n",
    "            dp1 = max(dp0 + nums[i]**2, nums[i]**2, dp1+nums[i])\n",
    "            dp0 = max(dp0 + nums[i], nums[i])\n",
    "            res = max(res, dp1, dp0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp0 = nums[0]\n",
    "        dp1 = nums[0] * nums[0]\n",
    "        ret = dp1\n",
    "        for i in range(1, n):\n",
    "            dp1 = max(dp1 + nums[i], dp0 + nums[i] * nums[i], nums[i] * nums[i])\n",
    "            dp0 = max(nums[i], dp0 + nums[i])\n",
    "            ret = max(dp1, ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "\n",
    "        res, dp0, dp1 = -float('inf'), -float('inf'), -float('inf')\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            \n",
    "            dp1 = max(dp0 + nums[i]**2, dp1 + nums[i], nums[i]**2)\n",
    "            dp0 = max(dp0 + nums[i], nums[i])\n",
    "            res = max(res, dp0, dp1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        dp = [nums[0], nums[0] * nums[0]]\n",
    "\n",
    "        n = len(nums)\n",
    "        res = dp[1]\n",
    "        for i in range(1, n):\n",
    "            dp[0] = max(0, dp[0])\n",
    "            dp[1] = max(nums[i] + dp[1], nums[i] * nums[i] + dp[0])\n",
    "            dp[0] += nums[i]\n",
    "            res = max(res, dp[1])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "\n",
    "        lastDP = 0\n",
    "        lastSDP = 0\n",
    "\n",
    "        max_sdp = lastSDP\n",
    "        for i in range(len(nums)):\n",
    "            s = nums[i] * nums[i]\n",
    "            lastSDP = max(lastSDP + nums[i], max(lastDP, 0) + s)\n",
    "            lastDP = max(lastDP, 0) + nums[i]\n",
    "            \n",
    "            max_sdp = max(max_sdp, lastSDP)\n",
    "\n",
    "        return max_sdp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        a, b = nums[0], nums[0] * nums[0]\n",
    "        ans = b\n",
    "        for i in range(1, n):\n",
    "            a = max(a, 0)\n",
    "            b = max(b + nums[i], a + nums[i] * nums[i])\n",
    "            a += nums[i]\n",
    "            ans = max(ans, b)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        dp0 = 0\n",
    "        dp1 = 0\n",
    "        for i in range(len(nums)):\n",
    "            dp1 = max(dp1 + nums[i], dp0 + nums[i] * nums[i])\n",
    "            dp0 = max(dp0 + nums[i], 0) \n",
    "            res = max(dp1, res)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        suffix = [0] * n\n",
    "        \"\"\"\n",
    "            我们要知道，对于当前元素i，它右边的最大连续和，也就是它右边的元素加上它右边元素的最长和大于0\n",
    "            suffix[i] = max(nums[i + 1] + suffix[i + 1], 0) \n",
    "        \"\"\"\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            suffix[i] = max(suffix[i + 1] + nums[i + 1], 0)\n",
    "        prefix = res = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            res = max(res, prefix + v * v + suffix[i])\n",
    "            prefix = max(prefix + v, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        dp_no_operate = [0 for _ in range(len(nums))]\n",
    "        dp_operate = [0 for _ in range(len(nums))]\n",
    "\n",
    "        dp_no_operate[0] = nums[0]\n",
    "        dp_operate[0] = nums[0]**2\n",
    "\n",
    "        # res = dp_operate[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            dp_no_operate[i] = max(dp_no_operate[i-1]+nums[i],nums[i])\n",
    "            dp_operate[i] = max([dp_operate[i-1]+nums[i],dp_no_operate[i-1]+nums[i]**2,nums[i]**2])\n",
    "        # print(dp_operate)\n",
    "        # print(dp_no_operate)\n",
    "        return max(dp_operate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "\n",
    "        dp1 = [0 for _ in range(len(nums)+1)]\n",
    "        dp2 = [0 for _ in range(len(nums)+1)]\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(1, len(nums)+1):\n",
    "            dp2[i] = max(dp2[i-1]+nums[i-1], dp1[i-1]+nums[i-1]*nums[i-1])\n",
    "            dp1[i] = max(dp1[i-1] + nums[i-1], 0)\n",
    "            res = max(dp2[i], res)\n",
    "            \n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        # 两个状态数组\n",
    "        # dp1[i]表示前i个数，不进行平方操作的最大子数组和\n",
    "        # dp2[i]表示前i个数，进行一次平方操作的最大子数组和\n",
    "        dp1 = [0] * n\n",
    "        dp2 = [0] * n\n",
    "        \n",
    "        dp1[0] = nums[0]\n",
    "        dp2[0] = nums[0] * nums[0]  # 对第一个数进行平方操作\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            # 不进行平方操作\n",
    "            dp1[i] = max(dp1[i - 1] + nums[i], nums[i])\n",
    "            # 进行平方操作\n",
    "            # 两种选择：1)在当前位置进行平方操作；2)前一个位置进行平方操作，然后累加当前数\n",
    "            dp2[i] = max(dp1[i - 1] + nums[i] * nums[i], dp2[i - 1] + nums[i], nums[i] * nums[i])\n",
    "        \n",
    "        # 返回两个状态数组中的最大值\n",
    "        return max(max(dp1), max(dp2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [0] * (n + 1)\n",
    "        g = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            x = nums[i] * nums[i]\n",
    "            f[i+1] = max(f[i] + nums[i], 0)\n",
    "            g[i+1] = max(f[i] + x, g[i] + nums[i], x)\n",
    "        return max(g)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0] * n for _ in range(2)]\n",
    "        dp[0][0] = nums[0]\n",
    "        dp[1][0] = nums[0] ** 2\n",
    "        for i in range(1, n):\n",
    "            dp[0][i] = nums[i] + max(0, dp[0][i - 1])\n",
    "            dp[1][i] = max(max(dp[0][i - 1], 0) + nums[i] ** 2, max(dp[1][i - 1], 0) + nums[i])\n",
    "        return max(dp[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        ## 状态机DP\n",
    "        n = len(nums)\n",
    "        f = [0] * (n + 1)\n",
    "        g = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            x = nums[i] * nums[i]\n",
    "            f[i+1] = max(f[i] + nums[i], 0)\n",
    "            g[i+1] = max(f[i] + x, g[i] + nums[i], x)\n",
    "        return max(g)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0] * n for _ in range(2)]\n",
    "        dp[0][0] = nums[0]\n",
    "        dp[1][0] = nums[0] ** 2\n",
    "        ans = dp[1][0]\n",
    "        for i in range(1, n):\n",
    "            dp[0][i] = nums[i] + max(0, dp[0][i - 1])\n",
    "            dp[1][i] = max(max(dp[0][i - 1], 0) + nums[i] ** 2, max(dp[1][i - 1], 0) + nums[i])\n",
    "            ans = max(dp[1][i], ans)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 前缀和\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0] * (n + 1)\n",
    "        post = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            pre[i+1] = pre[i] + nums[i] if pre[i] >= 0 else nums[i]\n",
    "            post[n-1-i] = post[n-i] + nums[n-1-i] if post[n-i] >= 0 else nums[n-1-i]\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            cur = nums[i] ** 2\n",
    "            cur += pre[i] if pre[i] > 0 else 0\n",
    "            cur += post[i+1] if post[i+1] > 0 else 0\n",
    "            ans = cur if cur > ans else ans\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp1=[0]*n #有一次操作\n",
    "        dp2=[0]*n #不操作\n",
    "        dp1[0]=nums[0]*nums[0]\n",
    "        dp2[0]=nums[0]\n",
    "        for  i in range(1,n):\n",
    "            dp1[i]=max(dp2[i-1]+nums[i]*nums[i],dp1[i-1]+nums[i],nums[i]*nums[i])\n",
    "            \n",
    "            dp2[i]=max(dp2[i-1]+nums[i],nums[i])\n",
    "        return max(dp1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        dp_no_operate = [0 for _ in range(len(nums))]\n",
    "        dp_operate = [0 for _ in range(len(nums))]\n",
    "\n",
    "        dp_no_operate[0] = nums[0]\n",
    "        dp_operate[0] = nums[0]**2\n",
    "\n",
    "        # res = dp_operate[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            dp_no_operate[i] = max(dp_no_operate[i-1]+nums[i],nums[i])\n",
    "            dp_operate[i] = max([dp_operate[i-1]+nums[i],dp_no_operate[i-1]+nums[i]**2,nums[i]**2])\n",
    "        # print(dp_operate)\n",
    "        # print(dp_no_operate)\n",
    "        return max(dp_operate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        dp = [[0] * len(nums) for _ in range(2)]\n",
    "        dp[0][0] = nums[0]\n",
    "        dp[1][0] = nums[0] * nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[0][i] = max(nums[i], dp[0][i-1] + nums[i])\n",
    "            dp[1][i] = max(dp[1][i-1] + nums[i], nums[i] ** 2, dp[0][i-1] + nums[i] ** 2)\n",
    "        return max(dp[1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        # 动态规划，用两个数组分别表示不替换和替换的最大子数组和\n",
    "        n=len(nums)\n",
    "        dp1=[nums[0]]+[0]*(n-1)\n",
    "        dp2=[nums[0]**2]+[0]*(n-1)\n",
    "        for i in range(1,n):\n",
    "            dp1[i]=max(dp1[i-1]+nums[i],nums[i])\n",
    "            dp2[i]=max(dp2[i-1]+nums[i],dp1[i-1]+nums[i]**2,nums[i]**2)\n",
    "        return max(dp2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        dp1, dp2 = [0]*N, [0]*N\n",
    "        dp1[0], dp2[0] = nums[0], max(nums[0]*nums[0], nums[0])\n",
    "        ans = max(dp1[0], dp2[0])\n",
    "        for i in range(1, N):\n",
    "            dp1[i] = max(dp1[i-1]+nums[i], 0)\n",
    "            dp2[i] = max(dp2[i-1]+nums[i], dp1[i-1]+nums[i]*nums[i])\n",
    "            ans = max(ans, dp2[i])\n",
    "        print(dp1, dp2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        dp = [[0] * 2 for _ in range(len(nums))]\n",
    "        res = float(-inf)\n",
    "        for i in range(len(nums)):\n",
    "            if i == 0:\n",
    "                dp[i][0] = nums[i] \n",
    "                dp[i][1] = nums[i] ** 2\n",
    "            else:\n",
    "                dp[i][0] = max(dp[i-1][0] + nums[i], nums[i])\n",
    "                dp[i][1] = max(dp[i-1][0] + nums[i] ** 2, dp[i-1][1] + nums[i], nums[i] ** 2)\n",
    "            res = max(res,dp[i][0],dp[i][1])\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0] * 2 for _ in range(n)]\n",
    "        dp[0][0] = nums[0]\n",
    "        dp[0][1] = nums[0] ** 2\n",
    "        ans = max(dp[0][0],dp[0][1])\n",
    "        for i in range(1, n):\n",
    "            # 前一个没用\n",
    "            dp[i][0] = max(dp[i-1][0] + nums[i],nums[i])\n",
    "            # 前面用过了\n",
    "            dp[i][1] = max(dp[i-1][0] + nums[i]*nums[i],dp[i-1][1]+nums[i],nums[i]*nums[i])\n",
    "            ans = max(ans,dp[i][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[-float('inf'),-float('inf')] for i in range(n+1)]\n",
    "        res = -float('inf')\n",
    "        for i in range(1,n+1):\n",
    "            dp[i][0] = max(dp[i-1][0]+nums[i-1],nums[i-1])\n",
    "            dp[i][1] = max(dp[i-1][0]+nums[i-1]*nums[i-1],nums[i-1]*nums[i-1],dp[i-1][1]+nums[i-1])\n",
    "            res = max(res,dp[i][0],dp[i][1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[-float('inf'),-float('inf')] for i in range(n+1)]\n",
    "        res = -float('inf')\n",
    "        for i in range(1,n+1):\n",
    "            dp[i][0] = max(dp[i-1][0]+nums[i-1],nums[i-1])\n",
    "            dp[i][1] = max(dp[i-1][0]+nums[i-1]*nums[i-1],nums[i-1]*nums[i-1],dp[i-1][1]+nums[i-1])\n",
    "            res = max(res,dp[i][0],dp[i][1])\n",
    "            # print(dp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        dp = [[0] * 2 for _ in range(len(nums))]\n",
    "        res = float(-inf)\n",
    "        for i in range(len(nums)):\n",
    "            if i == 0:\n",
    "                dp[i][0] = nums[i] \n",
    "                dp[i][1] = nums[i] ** 2\n",
    "            else:\n",
    "                dp[i][0] = max(dp[i-1][0] + nums[i], nums[i])\n",
    "                dp[i][1] = max(dp[i-1][0] + nums[i] ** 2, dp[i-1][1] + nums[i], nums[i] ** 2)\n",
    "                #dp[i][1]是，截止（包括）目前的nums[i]，使用了平方的，使用平方有几种情况，在前面就使用了，此时应该加原数字；前面都没使用，在这使用，加平方；平方\n",
    "            res = max(res,dp[i][0],dp[i][1])\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        res=-inf\n",
    "        dp=[[0]*2 for _ in range(n+1)] \n",
    "        for i in range(1,n+1):\n",
    "            dp[i][0]=max(dp[i-1][0],0)+nums[i-1]\n",
    "            dp[i][1]=max(max(dp[i-1][0],0)+nums[i-1]**2,max(dp[i-1][1],0)+nums[i-1])\n",
    "            res=max(res,dp[i][0],dp[i][1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        f = [[0,0] for _ in range(n)]\n",
    "\n",
    "        f[0][0] =nums[0]\n",
    "        f[0][1] = nums[0]**2\n",
    "\n",
    "        res = f[0][1]\n",
    "\n",
    "        for i in range(n):\n",
    "            f[i][0] = nums[i] if f[i-1][0] <=0 else f[i-1][0]+nums[i]\n",
    "            f[i][1] = max(f[i-1][0]+nums[i]**2,nums[i]**2,f[i-1][1]+nums[i])\n",
    "            res = max(res,f[i][1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0, 0] for _ in range(n)]\n",
    "        dp[0][0], dp[0][1] = nums[0], nums[0] * nums[0]\n",
    "        ans = dp[0][1]\n",
    "        for i in range(n):\n",
    "            dp[i][0] = max(dp[i - 1][0], 0) + nums[i]\n",
    "            dp[i][1] = max(dp[i - 1][1] + nums[i], max(dp[i - 1][0], 0) + nums[i] * nums[i])\n",
    "            ans = max(ans, dp[i][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "\n",
    "        # ln = len(nums)\n",
    "        # ans = -inf\n",
    "        # for i in range(ln):\n",
    "        #     dp = [0] * (ln+1)\n",
    "        #     tmp = copy.deepcopy(nums)\n",
    "        #     t = tmp[i]\n",
    "        #     tmp[i] = t ** 2\n",
    "        #     dp[0] = tmp[0]\n",
    "\n",
    "        #     for j in range(ln):\n",
    "        #         dp[j] = max(dp[j-1]+tmp[j], tmp[j])\n",
    "        #     ans = max(ans, max(dp))\n",
    "        # return ans\n",
    "\n",
    "        ln = len(nums)\n",
    "        ans = nums[0] **2\n",
    "        dp = [[0,0] for _ in range(ln)]\n",
    "        dp[0][0] = nums[0]\n",
    "        dp[0][1] = nums[0] **2\n",
    "        \n",
    "        for i in range(ln):\n",
    "            dp[i][0] = max(nums[i] ,dp[i-1][0] + nums[i]) # （当前，和前一值+当前值）\n",
    "            dp[i][1] = max(dp[i-1][0] + nums[i] **2, nums[i] **2, dp[i-1][1] + nums[i]) \n",
    "            # 需要比较（前一个值未变+当前变，当前变，前一个变+当前值）\n",
    "            ans = max(ans, dp[i][1])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        dp = [[0, 0] for _ in range(len(nums))]\n",
    "        dp[0][0] = nums[0]\n",
    "        dp[0][1] = nums[0] ** 2\n",
    "        if len(nums) == 1:\n",
    "            return nums[0] ** 2\n",
    "        ans = -math.inf\n",
    "        for i in range(1, len(nums)):\n",
    "            dp[i][0] = max(dp[i-1][0] + nums[i], nums[i])\n",
    "            dp[i][1] = max(dp[i-1][1] + nums[i], dp[i-1][0] + nums[i] ** 2, nums[i] ** 2)\n",
    "            ans = max(ans, dp[i][1])\n",
    "            ans = max(ans, dp[i][0])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[-float('inf'),-float('inf')] for i in range(n+1)]\n",
    "        res = -float('inf')\n",
    "        for i in range(1,n+1):\n",
    "            dp[i][0] = max(dp[i-1][0]+nums[i-1],nums[i-1])\n",
    "            dp[i][1] = max(dp[i-1][0]+nums[i-1]*nums[i-1],nums[i-1]*nums[i-1],dp[i-1][1]+nums[i-1])\n",
    "            res = max(res,dp[i][0],dp[i][1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[[-float(\"inf\")]*2 for _ in range(n)]\n",
    "        dp[0][0]=nums[0]\n",
    "        dp[0][1]=nums[0]*nums[0]\n",
    "        mx=max(dp[0])\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=max(nums[i], dp[i-1][0]+nums[i] )\n",
    "            dp[i][1]=max(nums[i]*nums[i],dp[i-1][1]+nums[i],dp[i-1][0]+nums[i]*nums[i])\n",
    "\n",
    "            mx=max(mx,max(dp[i]))\n",
    "        return mx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        N=len(nums)\n",
    "        dp=[[-inf]*2 for i in range(N)]\n",
    "        dp[0][0]=nums[0]\n",
    "        dp[0][1]=nums[0]**2\n",
    "        ans=dp[0][1]\n",
    "        for i in range(1,N):\n",
    "            dp[i][0]=max(dp[i-1][0],0)+nums[i]\n",
    "            dp[i][1]=max(max(dp[i-1][0],0)+nums[i]**2,dp[i-1][1]+nums[i])\n",
    "            ans=max(ans,dp[i][0],dp[i][1])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [[-inf] * 2 for _ in range(n+1)]\n",
    "\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            f[i+1][0] = max(f[i][0] + x, x)\n",
    "            f[i+1][1] = max(f[i][0] + x * x, x * x, f[i][1] + x)\n",
    "            ans = max(ans, f[i+1][0], f[i+1][1])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[[0 for _ in range(2)]for _ in range(n)]\n",
    "        dp[0][0]=nums[0]\n",
    "        dp[0][1]=nums[0]*nums[0]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=max(dp[i-1][0],0)+nums[i]\n",
    "            dp[i][1]=max(max(dp[i-1][0],0)+nums[i]*nums[i],max(dp[i-1][1],0)+nums[i])\n",
    "        ans=-float(\"inf\")\n",
    "        for i in range(n):\n",
    "            ans=max(ans,dp[i][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        # # 0 无替换 1 已有替换但不是当前 2 替换当前这个\n",
    "        # n = len(nums)\n",
    "        # res = 0\n",
    "        # dp = [[[0]*3 for i in range(n)] for j in range(n)]\n",
    "        # for i in range(n):\n",
    "        #     # 优化存储空间 n*n*3 -> n*3\n",
    "        #     dp[i][i][0] = nums[i]\n",
    "        #     dp[i][i][1] = nums[i]\n",
    "        #     dp[i][i][2] = nums[i]**2 \n",
    "        #     res = max(res, dp[i][i][2])\n",
    "        #     # dp[i][j] 表示 i到j 的子数组的和\n",
    "        #     for j in range(i+1, n):\n",
    "        #         dp[i][j][0] = dp[i][j-1][0] + nums[j]\n",
    "        #         dp[i][j][1] = max(dp[i][j-1][1] + nums[j], dp[i][j-1][2]+nums[j])\n",
    "        #         dp[i][j][2] = dp[i][j-1][0] + nums[j]*nums[j]\n",
    "        #         res = max(res, dp[i][j][0], dp[i][j][1], dp[i][j][2])\n",
    "        # # print(dp)   \n",
    "        # return res \n",
    "\n",
    "        # 0 未发生替换 1 已有替换但不是当前 2 替换当前这个\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        dp = [[0]*3 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            # 优化存储空间 n*n*3 -> n*3\n",
    "            # prev = dp\n",
    "            if i == 0:\n",
    "                dp[i][0] = nums[i]\n",
    "                dp[i][1] = nums[i]\n",
    "                dp[i][2] = nums[i]**2 \n",
    "                res = max(res, dp[i][2])\n",
    "            # dp[j] 表示 i到j 的子数组的和\n",
    "            else:\n",
    "                dp[i][0] = max(dp[i-1][0], 0) + nums[i]\n",
    "                dp[i][1] = max(dp[i-1][1] + nums[i], dp[i-1][2]+nums[i])\n",
    "                dp[i][2] = max(dp[i-1][0], 0) + nums[i]*nums[i]\n",
    "                res = max(res, dp[i][0], dp[i][1], dp[i][2])\n",
    "            # prev = dp\n",
    "            # print(prev)\n",
    "        # print(dp)   \n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterOperation(self, nums: List[int]) -> int:\n",
    "        # dp[i][j] =\n",
    "        dp = [[0, 0] for _ in nums]\n",
    "        result = 0\n",
    "        for idx, num in enumerate(nums):\n",
    "            if idx == 0:\n",
    "                dp[idx][0] = nums[idx]\n",
    "                dp[idx][1] = nums[idx]**2\n",
    "            else:\n",
    "                dp[idx][0] = max(dp[idx-1][0] + nums[idx], nums[idx])\n",
    "                dp[idx][1] = max(dp[idx-1][0] + nums[idx]**2, dp[idx-1][1] + nums[idx], nums[idx]**2)\n",
    "            result = max(dp[idx][0], dp[idx][1], result)\n",
    "        print(dp)\n",
    "        return result\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
